package Leetcode.动态规划;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/3/25 15:22
 * @Description:
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 *
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 *
 * 假设每一种面额的硬币有无限个。
 *
 * 题目数据保证结果符合 32 位带符号整数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：amount = 5, coins = [1, 2, 5]
 * 输出：4
 * 解释：有四种方式可以凑成总金额：
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * 示例 2：
 *
 * 输入：amount = 3, coins = [2]
 * 输出：0
 * 解释：只用面额 2 的硬币不能凑成总金额 3 。
 * 示例 3：
 *
 * 输入：amount = 10, coins = [10]
 * 输出：1
 *
 * 1 <= coins.length <= 300
 * 1 <= coins[i] <= 5000
 * coins 中的所有值 互不相同
 * 0 <= amount <= 5000
 */

public class coinChange2 {
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
        System.out.println(change(amount, coins));
    }

    // 定义一个静态方法change2，接收两个参数：amount和coins数组
    public static int change2(int amount, int[] coins) {
        // 获取coins数组的长度
        int n = coins.length;
        // 创建一个二维数组f，行数为n+1，列数为amount+1
        int[][] f = new int[n + 1][amount + 1];
        // 初始化f[0][0]为1，代表总金额为0时，有一种方法（不使用任何硬币）
        //f[n][m]代表用n个硬币能够凑成m的组合数
        f[0][0] = 1;

        // 遍历coins数组
        for (int i = 0; i < n; i++) {
            // 遍历可能的金额，从0到amount
            for (int currentMoney = 0; currentMoney <= amount; currentMoney++) {
                // 如果当前金额c小于coins[i]，那么只能使用前i-1种硬币
                if (currentMoney < coins[i]) {
                    f[i + 1][currentMoney] = f[i][currentMoney];
                } else {
                    // 否则，可以继续使用当前硬币或者不使用
                    f[i + 1][currentMoney] = f[i][currentMoney] + f[i + 1][currentMoney - coins[i]];
                }
            }
        }
        // 返回使用所有硬币组合得到amount的所有可能方式的数量
        return f[n][amount];
    }



    // 定义一个静态方法change，接收两个参数：amount和coins数组
    public static int change(int amount, int[] coins) {
        // 创建一个一维数组dp，大小为amount + 1，用于存储动态规划的状态
        int[] dp = new int[amount + 1];
        // 初始化dp[0]为1，代表总金额为0时，有一种方法（不使用任何硬币）
        dp[0] = 1;

        // 遍历coins数组中的每一枚硬币
        for (int coin : coins) {
            // 对于每一枚硬币，更新dp数组中大于等于coin的金额的值
            for (int i = coin; i <= amount; i++) {
                 dp[i] += dp[i - coin];
                // 表示组合硬币得到金额i的所有可能方式的数量
                // 是之前组合金额i - coin的所有可能方式的数量加上当前硬币的组合方式
            }
        }
        // 返回使用所有硬币组合得到amount的所有可能方式的数量
        return dp[amount];
    }

}
